Falling squares [Offline Prop,Segment Tree, Block Decomp,Brute Force]¶
Time: O(NLogN); Space: O(N); hard
On an infinite number line (x-axis), we drop given squares in the order they are given.
The i-th square dropped (positions[i] = (left, side_length)) is a square with the left-most point being positions[i][0] and sidelength positions[i][1].
The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently landed squares. We wait for each square to stick before dropping the next.
The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they touch (either the number line or another square). Squares dropped adjacent to each other will not stick together prematurely.
Return a list ans of heights. Each height ans[i] represents the current highest height of any square we have dropped, after dropping squares represented by positions[0], positions[1], …, positions[i].
Example 1:
Input: positions = [[1,2], [2,3], [6,1]]
Output: [2, 5, 5]
Explanation:
After the first drop of positions[0] = [1,2]:
_aa
_aa The maximum height of any square is 2.
After the second drop of positions[1] = [2,3]:
__aaa
__aaa
__aaa
_aa__
_aa__ The maximum height of any square is 5.
The larger square stays on top of the smaller square despite where its center of gravity is, because squares are infinitely sticky on their bottom edge.
After the third drop of positions[1] = [6,1]:
__aaa
__aaa
__aaa *_aa
_aa___a The maximum height of any square is still 5.
Thus, we return an answer of [2, 5, 5]
Example 2:
Input: positions = [[100,100], [200,100]]
Output: [100,100]
Explanation:
Adjacent squares don’t get stuck prematurely - only their bottom edge can stick to surfaces.
Constraints:
1 <= len(positions) <= 1000.
1 <= positions[0] <= 10^8.
1 <= positions[1] <= 10^6.
Hints:
If positions = [[10, 20], [20, 30]], this is the same as [[1, 2], [2, 3]]. Currently, the values of positions are very large. Can you generalize this approach so as to make the values in positions manageable?
1. Offline Propagation [O(N^2), O(N)]¶
Intuition
Instead of asking the question “what squares affect this query?”, lets ask the question “what queries are affected by this square?”
Algorithm
Let qans[i] be the maximum height of the interval specified by positions[i]. At the end, we’ll return a running max of qans.
For each square positions[i], the maximum height will get higher by the size of the square we drop. Then, for any future squares that intersect the interval [left, right) (where left = positions[i][0], right = positions[i][0] + positions[i][1]), we’ll update the maximum height of that interval.
[1]:
class Solution1(object):
"""
Time: O(N^2), where N is the length of positions. We use two for-loops, each of complexity O(N).
Space: O(N), the space used by qans and ans.
"""
def fallingSquares(self, positions):
"""
:type positions: List[List[int]]
:rtype: List[int]
"""
qans = [0] * len(positions)
for i, (left, size) in enumerate(positions):
right = left + size
qans[i] += size
for j in range(i+1, len(positions)):
left2, size2 = positions[j]
right2 = left2 + size2
if left2 < right and left < right2: # intersect
qans[j] = max(qans[j], qans[i])
ans = []
for x in qans:
ans.append(max(ans[-1], x) if ans else x)
return ans
[2]:
s = Solution1()
positions = [[1,2], [2,3], [6,1]]
assert s.fallingSquares(positions) == [2, 5, 5]
positions = [[100,100], [200,100]]
assert s.fallingSquares([[100, 100], [200, 100]]) == [100, 100]
2. Segment Tree with Lazy Propagation [O(NLogN), O(N)]¶
Intuition
If we were familiar with the idea of a segment tree (which supports queries and updates on intervals), we can immediately crack the problem.
Algorithm
Segment trees work by breaking intervals into a disjoint sum of component intervals, whose number is at most log(width). The motivation is that when we change an element, we only need to change log(width) many intervals that aggregate on an interval containing that element.
When we want to update an interval all at once, we need to use lazy propagation to ensure good run-time complexity. This topic is covered in more depth here.
With such an implementation in hand, the problem falls out immediately.
[3]:
class SegmentTree(object):
def __init__(self, N, update_fn, query_fn):
self.N = N
self.H = 1
while (1 << self.H) < N:
self.H += 1
self.update_fn = update_fn
self.query_fn = query_fn
self.tree = [0] * (2 * N)
self.lazy = [0] * N
def __apply(self, x, val):
self.tree[x] = self.update_fn(self.tree[x], val)
if x < self.N:
self.lazy[x] = self.update_fn(self.lazy[x], val)
def __pull(self, x):
while x > 1:
x //= 2
self.tree[x] = self.query_fn(self.tree[x*2], self.tree[x*2 + 1])
self.tree[x] = self.update_fn(self.tree[x], self.lazy[x])
def __push(self, x):
for h in range(self.H, 0, -1):
y = x >> h
if self.lazy[y]:
self.__apply(y*2, self.lazy[y])
self.__apply(y*2 + 1, self.lazy[y])
self.lazy[y] = 0
def update(self, L, R, h):
L += self.N
R += self.N
L0, R0 = L, R
while L <= R:
if L & 1:
self.__apply(L, h)
L += 1
if R & 1 == 0:
self.__apply(R, h)
R -= 1
L //= 2; R //= 2
self.__pull(L0)
self.__pull(R0)
def query(self, L, R):
L += self.N
R += self.N
self.__push(L); self.__push(R)
result = 0
while L <= R:
if L & 1:
result = self.query_fn(result, self.tree[L])
L += 1
if R & 1 == 0:
result = self.query_fn(result, self.tree[R])
R -= 1
L //= 2; R //= 2
return result
[4]:
import bisect
class Solution2(object):
"""
Time: O(NLogN)
Space: O(N)
"""
def fallingSquares(self, positions):
"""
:type positions: List[List[int]]
:rtype: List[int]
"""
index = set()
for left, size in positions:
index.add(left);
index.add(left+size-1)
index = sorted(list(index))
tree = SegmentTree(len(index), max, max)
max_height = 0
result = []
for left, size in positions:
L, R = bisect.bisect_left(index, left), bisect.bisect_left(index, left+size-1)
h = tree.query(L, R) + size
tree.update(L, R, h)
max_height = max(max_height, h)
result.append(max_height)
return result
[5]:
s = Solution2()
positions = [[1,2], [2,3], [6,1]]
assert s.fallingSquares(positions) == [2, 5, 5]
positions = [[100,100], [200,100]]
assert s.fallingSquares([[100, 100], [200, 100]]) == [100, 100]
3. Block (Square Root) Decomposition [O(N*sqrt(N)),O(N)]¶
Intuition
Whenever we perform operations (like update and query) on some interval in a domain, we could segment that domain with size W into blocks of size sqrt(W).
Then, instead of a typical brute force where we update our array heights representing the board, we will also hold another array blocks, where blocks[i] represents the B = [sqrt(W)] elements heights[B*i], heights[B*i + 1], …, heights[B*i + B-1]. This allows us to write to the array in O(B)O(B) operations.
Algorithm
Let’s get into the details. We actually need another array, blocks_read. When we update some element i in block b = i / B, we’ll also update blocks_read[b]. If later we want to read the entire block, we can read from here (and stuff written to the whole block in blocks[b].)
When we write to a block, we’ll write in blocks[b]. Later, when we want to read from an element i in block b = i / B, we’ll read from heights[i] and blocks[b].
Our process for managing query and update will be similar. While left isn’t a multiple of B, we’ll proceed with a brute-force-like approach, and similarly for right. At the end, [left, right+1) will represent a series of contiguous blocks: the interval will have length which is a multiple of B, and left will also be a multiple of B.
[6]:
import bisect
class Solution3(object):
'''
Time: O(N*sqrt(N))
Space: O(N)
'''
def fallingSquares(self, positions):
'''
:type positions: List[List[int]]
:rtype: List[int]
'''
def query(heights, left, right, B, blocks, blocks_read):
result = 0
while left % B and left <= right:
result = max(result, heights[left], blocks[left//B])
left += 1
while right % B != B-1 and left <= right:
result = max(result, heights[right], blocks[right//B])
right -= 1
while left <= right:
result = max(result, blocks[left//B], blocks_read[left//B])
left += B
return result
def update(heights, left, right, B, blocks, blocks_read, h):
while left % B and left <= right:
heights[left] = max(heights[left], h)
blocks_read[left//B] = max(blocks_read[left//B], h)
left += 1
while right % B != B-1 and left <= right:
heights[right] = max(heights[right], h)
blocks_read[right//B] = max(blocks_read[right//B], h)
right -= 1
while left <= right:
blocks[left//B] = max(blocks[left//B], h)
left += B
index = set()
for left, size in positions:
index.add(left);
index.add(left+size-1)
index = sorted(list(index))
W = len(index)
B = int(W**.5)
heights = [0] * W
blocks = [0] * (B+2)
blocks_read = [0] * (B+2)
max_height = 0
result = []
for left, size in positions:
L, R = bisect.bisect_left(index, left), bisect.bisect_left(index, left+size-1)
h = query(heights, L, R, B, blocks, blocks_read) + size
update(heights, L, R, B, blocks, blocks_read, h)
max_height = max(max_height, h)
result.append(max_height)
return result
[7]:
s = Solution3()
positions = [[1,2], [2,3], [6,1]]
assert s.fallingSquares(positions) == [2, 5, 5]
positions = [[100,100], [200,100]]
assert s.fallingSquares([[100, 100], [200, 100]]) == [100, 100]
4. Brute Force with Coordinate Compression [O(N^2),O(N)]¶
Intuition and Algorithm
Let N = len(positions). After mapping the board to a board of length at most 2* N <= 2000, we can brute force the answer by simulating each square’s drop directly.
Our answer is either the current answer or the height of the square that was just dropped, and we’ll update it appropriately.
Coordinate Compression
In the below approaches, since there are only up to 2 * len(positions) critical points, namely the left and right edges of each square, we can use a technique called coordinate compression to map these critical points to adjacent integers, as shown in the code snippets below.
For brevity, these snippets are omitted from the remaining solutions.
[8]:
class Solution4(object):
"""
Time: O(N^2), where N is the length of positions. We use two for-loops, each of complexity O(N)
(because of coordinate compression.)
Space: O(N), the space used by heights.
"""
def fallingSquares(self, positions):
'''
:type positions: List[List[int]]
:rtype: List[int]
'''
# Coordinate Compression
coords = set()
for left, size in positions:
coords.add(left)
coords.add(left + size - 1)
index = {x: i for i, x in enumerate(sorted(coords))}
heights = [0] * len(index)
def query(L, R):
return max(heights[i] for i in range(L, R+1))
def update(L, R, h):
for i in range(L, R+1):
heights[i] = max(heights[i], h)
best = 0
ans = []
for left, size in positions:
L = index[left]
R = index[left + size - 1]
h = query(L, R) + size
update(L, R, h)
best = max(best, h)
ans.append(best)
return ans
[9]:
s = Solution4()
positions = [[1,2], [2,3], [6,1]]
assert s.fallingSquares(positions) == [2, 5, 5]
positions = [[100,100], [200,100]]
assert s.fallingSquares([[100, 100], [200, 100]]) == [100, 100]
5. [O(N^2), O(N)]¶
[10]:
class Solution5(object):
'''
Time: O(N^2)
Space: O(N)
'''
def fallingSquares(self, positions):
'''
:type positions: List[List[int]]
:rtype: List[int]
'''
heights = [0] * len(positions)
for i in range(len(positions)):
left_i, size_i = positions[i]
right_i = left_i + size_i
heights[i] += size_i
for j in range(i+1, len(positions)):
left_j, size_j = positions[j]
right_j = left_j + size_j
if left_j < right_i and left_i < right_j: # intersect
heights[j] = max(heights[j], heights[i])
result = []
for height in heights:
result.append(max(result[-1], height) if result else height)
return result
[11]:
s = Solution5()
positions = [[1,2], [2,3], [6,1]]
assert s.fallingSquares(positions) == [2, 5, 5]
positions = [[100,100], [200,100]]
assert s.fallingSquares([[100, 100], [200, 100]]) == [100, 100]